package uestc.lj.basicPromotion.dfs;

/**
 * @Author:Crazlee
 * @Date:2021/11/28
 */
public class Code03_CoinsMin {

	public static int minCoins1(int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim < 0) {
			return -1;
		}
		return process1(arr, 0, aim);
	}

	// 当前考虑的面值是arr[i]，还剩rest的钱需要找零
	// 如果返回-1说明自由使用arr[i..N-1]面值的情况下，无论如何也无法找零rest
	// 如果返回不是-1，代表自由使用arr[i..N-1]面值的情况下，找零rest需要的最少张数

	public static int process1(int[] arr, int i, int rest) {
		// base case：
		// 已经没有面值能够考虑了
		// 如果此时剩余的钱为0，返回0张
		// 如果此时剩余的钱不是0，返回-1
		if (i == arr.length) {
			return rest == 0 ? 0 : -1;
		}
		// 最少张数，初始时为-1，因为还没找到有效解
		int res = -1;
		// 依次尝试使用当前面值(arr[i])0张、1张、k张，但不能超过rest
		for (int k = 0; k * arr[i] <= rest; k++) {
			// 使用了k张arr[i]，剩下的钱为rest - k * arr[i]
			// 交给剩下的面值去搞定(arr[i+1..N-1])
			int next = process1(arr, i + 1, rest - k * arr[i]);
			// 说明这个后续过程有效
			if (next != -1) {
				res = res == -1 ? next + k : Math.min(res, next + k);
			}
		}
		return res;
	}

	//===============================================================================================

	public static int minCoins2(int[] arr, int aim) {
		return process2(arr, 0, aim);
	}

	public static int process2(int[] arr, int index, int rest) {
		if (rest < 0) {
			return -1;
		}
		if (rest == 0) {
			return 0;
		}
		if (index == arr.length) {
			return -1;
		}
		int unUsed = process2(arr, index + 1, rest);
		int used = process2(arr, index + 1, rest - arr[index]);
		if (unUsed == -1 && used == -1) {
			return -1;
		} else {
			if (unUsed == -1) {
				return used + 1;
			}
			if (used == -1) {
				return unUsed;
			}
			return Math.min(unUsed, used + 1);
		}
	}

	//===============================================================================================

	public static int minCoins3(int[] arr, int aim) {
		int[][] dp = new int[arr.length + 1][aim + 1];

		for (int i = 0; i <= arr.length; i++) {
			for (int j = 0; j <= aim; j++) {
				dp[i][j] = -2;
			}
		}
		return process3(arr, 0, aim, dp);
	}

	private static int process3(int[] arr, int index, int rest, int[][] dp) {
		if (rest < 0) {
			return -1;
		}
		if (dp[index][rest] != -2) {
			return dp[index][rest];
		}
		if (rest == 0) {
			dp[index][rest] = 0;
		} else if (index == arr.length) {
			dp[index][rest] = -1;
		} else {
			int unUsed = process3(arr, index + 1, rest, dp);
			int used = process3(arr, index + 1, rest - arr[index], dp);
			if (unUsed == -1 && used == -1) {
				dp[index][rest] = -1;
			} else {
				if (unUsed == -1) {
					dp[index][rest] = used + 1;
				} else if (used == -1) {
					dp[index][rest] = unUsed;
				} else {
					dp[index][rest] = Math.min(unUsed, used + 1);
				}
			}
		}
		return dp[index][rest];
	}

	//=================================================================================================

	public static int minCoins4(int[] arr, int aim) {
		int[][] dp = new int[arr.length + 1][aim + 1];

		for (int i = 0; i <= arr.length; i++) {
			dp[i][0] = 0;
		}

		for (int j = 1; j <= aim; j++) {
			dp[arr.length][j] = -1;
		}

		for (int index = arr.length - 1; index >= 0; index--) {
			for (int rest = 1; rest <= aim; rest++) {
				int unUsed = dp[index + 1][rest];
				int used = rest - arr[index] < 0 ? -1 : dp[index + 1][rest - arr[index]];
				if (unUsed == -1 && used == -1) {
					dp[index][rest] = -1;
				} else {
					if (unUsed == -1) {
						dp[index][rest] = used + 1;
					} else if (used == -1) {
						dp[index][rest] = unUsed;
					} else {
						dp[index][rest] = Math.min(unUsed, used + 1);
					}
				}
			}
		}
		return dp[0][aim];
	}

	public static void main(String[] args) {
		int[] coins = {1, 2, 5};
		int amount = 11;
		System.out.println(minCoins2(coins, amount));
	}
}
